Suppose I have a recursive callback such as this (but more complex):
const weightedFactorial = useCallback(n => {
if (n === 0) {
return 1;
}
return weight * n * weightedFactorial(n - 1);
},[weight]);
Is there a way to store previously calculated values, such that if the function is called on a repeated index, it is possible to skip the recursion?
const value1 = weightedFactorial(60)
// Calculate recursively
const value2 = weightedFactorial(30)
// This value should already be known
// and the calculation should be skipped
I've tried to keep a state with known values but I seem to get stuck in a loop, probably because it needs to be a dependency of the callback,
const [knownValues, setKnownValues] = useState([{ n: 0, value: 1 }]);
const weightedFactorial = useCallback(n => {
const known = knownValues.find(known => known.n === n);
if (known?.value) {
return known.value;
}
const newValue = weight * n * weightedFactorial(n - 1);
setKnownValues(knownValues => [...knownValues, { n, value: newValue }]);
return newValue;
},[knownValues, weight]);
The easiest way to store results for memoisation is a Map, or an array if your function parameter is a positive integer:
function FactorialExamples(props) {
const results = [1];
const factorial = n => {
if (n in results) return results[n]; // also takes care of our base case n==0
return results[n] = n * factorial(n-1);
};
return <p>
5!: { factorial(5) }
<br />
10!: { factorial(10) }
</p>;
}
This will work nicely and not compute factorials more than once if you call factorial multiple times. However, it will still redo the computation on every rendering of your function component. To persist the results across re-renders, move the results variable out of the function into the module scope, or put it inside a reference (that will be stored once per mounted component):
function Factorial(props) {
const results = useRef([1]).current;
const factorial = n => {
if (n in results) return results[n];
return results[n] = n * factorial(n-1);
};
return <p>
{props.n}!: { factorial(props.n) }
</p>;
}
function Demo() {
const [value, setValue] = useState(0);
return <div>
<input type="number" value={value} onInput=(e => setValue(e.currentTarget.valueAsNumber)} min="0" />
<Factorial n={value} />
</div>;
}
But you have a more complicated case: the weightedFactorial also depends on a weight state, not just on its argument1. You could reset the reference every time the weight changes, but that's complicated and error-prone.
Instead, use an approach similar to your useCallback, that switches out the results store together with the "callback". Instead of useCallback, use useMemo and return a closure from it:
const weightedFactorial = useMemo(() => {
const results = [1];
return n => {
if (n in results) return results[n];
return weight * n * weightedFactorial(n - 1);
};
}, [weight]);
1: Of course, you could just treat both weight and n as arguments, and use a standard approach for memoising functions with multiple arguments (see also here). Then the results could again be stored statically or in a reference.
You can use React.useMemo to calculate the value on the first render or when a dependency changes. But maybe you are referring to memoization so that a previously calculate value doesn't need other computation.
https://www.30secondsofcode.org/js/s/memoize or https://www.digitalocean.com/community/tutorials/js-understanding-recursion
You can combine both useMemo and memoization to achieve what you need.